1. Field of the Invention
This invention relates generally to computer systems, and, more particularly, to multiprocessor systems wherein multiple processors implement virtual memory and access a shared memory.
2. Description of the Related Art
A typical computer system includes a memory hierarchy to obtain a relatively high level of performance at a relatively low cost. Instructions of several different software programs are typically stored on a relatively large but slow non-volatile storage unit (e.g., a disk drive unit). When a user selects one of the programs for execution, the instructions of the selected program are copied into a main memory, and a processor (e.g., a central processing unit or CPU) obtains the instructions of the selected program from the main memory. Well-known virtual memory management techniques allow the processor to access data structures larger in size than that of the main memory by storing only a portion of the data structures within the main memory at any given time. Remainders of the data structures are stored within the relatively large but slow non-volatile storage unit, and are copied into the main memory only when needed.
Virtual memory is typically implemented by dividing an address space of the processor into multiple blocks called page frames or xe2x80x9cpages.xe2x80x9d Only data corresponding to a portion of the pages is stored within the main memory at any given time. When the processor generates an address within a given page, and a copy of that page is not located within the main memory, the required page of data is copied from the relatively large but slow non-volatile storage unit into the main memory. In the process, another page of data may be copied from the main memory to the non-volatile storage unit to make room for the required page.
Popular processor architectures (e.g., the 80x86 or xe2x80x9cx86xe2x80x9d processor architecture) typically include specialized hardware elements to support implementation of virtual memory. For example, the x86 processor architecture includes specialized hardware elements to support a protected virtual address mode (i.e., a protected mode). Such processors produce virtual addresses, and implement virtual-to-physical address translation mechanisms to xe2x80x9cmapxe2x80x9d the virtual addresses to physical addresses of memory locations in the main memory. The address translation mechanisms typically include one or more data structures (i.e., xe2x80x9cpage tablesxe2x80x9d) arranged to form a hierarchy. The page tables are typically stored in the main memory and are maintained by operating system software (i.e., an operating system). A highest-ordered page table (e.g., the x86 page directory) is always located within the main memory. Any additional page tables may be obtained from the storage unit and stored in the main memory as needed.
A base address of a memory page containing the highest-ordered page table (e.g., the x86 page directory) is typically stored in a register. The highest-ordered page table includes multiple entries. The entries may be base addresses of other page tables, or base addresses of pages including physical addresses corresponding to virtual addresses. Where multiple page tables are used to perform the virtual-to-physical address translation, entries of the highest-ordered page table are base addresses of other page tables. A virtual address produced by the processor is divided into multiple portions, and the portions are used as indexes into the page tables.
A lowest-ordered page table includes an entry storing a base address of the page including the physical address corresponding to the virtual address. The physical address is formed by adding a lowest-ordered or xe2x80x9coffsetxe2x80x9d portion of the virtual address to the base address in the selected entry of the lowest-ordered page table.
The above described virtual-to-physical address translation mechanism requires accessing one or more page tables in main memory (i.e., page table xe2x80x9clookupsxe2x80x9d or xe2x80x9cwalksxe2x80x9d). Such page table accesses require significant amounts of time, and negatively impact processor performance. Consequently, processors typically include a translation look-aside buffer (TLB) for storing the most recently used page table entries. TLB entries are typically maintained by the operating system. Inclusion of the TLB significantly increases processor performance.
It would be beneficial to extend the benefits of virtual memory to multiprocessor systems including multiple processors. Such multiprocessor systems may advantageously have a main memory shared by all of the processors. The ability of all processors to access instructions and data (i.e., xe2x80x9ccodexe2x80x9d) stored in the shared main memory eliminates the need to copy code from one memory accessed exclusively by one processor to another memory accessed exclusively by another processor. Additionally, a portion of the shared main memory may be used for interprocess communication.
Several problems arise in multiprocessor systems implementing virtual memory and having a shared main memory. One problem is how to create and maintain virtual memory data structures (e.g., page tables), and how to coordinate transfers of pages between the main memory and one or more storage units. Another problem, referred to herein as the xe2x80x9cTLB coherence problem,xe2x80x9d arises when each of the multiple processors expectedly has its own performance-enhancing TLB. As described above, each page table entry corresponds to a different page in the shared main memory. When one of the processors replaces a page in the shared main memory with a page from the storage unit, TLB entries corresponding to the replaced page in the other processors become invalid. One or more of the other processors may use such invalid page table entries in their TLBs to perform virtual-to-physical address translations, thereby accessing wrong pages in memory, and possibly causing incorrect results to be produced and/or other errors in system operation.
Moreover, to further preclude page table accesses in main memory, write accesses to pages in main memory may be recorded in xe2x80x9cdirtyxe2x80x9d bits stored in the TLBs rather than having to access dirty bits of the corresponding page table entries in the shared main memory. Not having visibility into the TLBs of the other processors, a processor replacing a page in the shared main memory may not know that one of the other processors had previously written to the replaced page, and thus may not write the replaced page back to storage. As a result, data in the replaced page may not be correct, possibly causing incorrect results to be produced and/or other errors in system operation.
The present invention is directed to a system which implements a method that may solve, or at least reduce, some or all of the aforementioned problems.
A computer system is presented including a first processor, a second processor in communication with the first processor, and a memory coupled to the first and second processors (i.e., a shared memory) and including multiple memory locations, and a storage device coupled to the first processor. The first and second processors implement virtual memory using the memory. The first processor maintains a first set of page tables and a second set of page tables in the memory, and uses the first set of page tables to access the memory locations within the memory. The second processor uses the second set of page tables, maintained by the first processor, to access the memory locations within the memory.
The first and second sets of page tables may include at least one page table. The first processor may use the first set of page tables to translate a virtual address generated within the first processor to a corresponding physical address of a memory location within the memory, and may use the physical address of the memory location to access the memory location. Similarly, the second processor may use the second set of page tables to translate a virtual address generated within the second processor to a corresponding physical address of a memory location within the memory, and may use the physical address of the memory location to access the memory location.
The second set of page tables may include multiple page table entries. Each of the page table entries may be used to store a base address of a corresponding memory page when the corresponding memory page is present in the memory. The second processor may include a buffer, wherein the buffer includes multiple entries for storing recently used page table entries and recording write accesses by the second processor to the corresponding memory pages. Before replacing a memory page present in the memory with a memory page stored in the storage device, the first processor may inform the second processor of a need to remove any entries of the buffer corresponding to a physical address range of the memory page to be replaced.
A virtual memory page replacement method is described for use in a computer system including a first and second processor, wherein the virtual memory page replacement method is designed to help maintain paged memory coherence within the multiprocessor computer system. In one embodiment, the method includes accessing each page table entry of a set of page table entries of the second processor. Each page table entry of the set of page table entries corresponds to a different memory page (i.e., page) of a set of pages of the second processor. Each page of the set of pages of the second processor is stored in a memory and corresponds to a first page of the first processor to be removed from the memory. Each page table entry of the second processor includes a dirty (D) bit indicating whether or not the corresponding page of the second processor needs to be written to a storage.
Each page table entry of the set of page table entries is marked to indicate the corresponding page of the second processor is not present in the memory. For example, a present (P) bit of each page table entry of the set of page table entries may be changed (e.g., xe2x80x9cclearedxe2x80x9d or set to logic xe2x80x980xe2x80x99) to indicate the corresponding page of the second processor is not present in the memory. The second processor is informed of a need to remove any entry of a buffer of the second processor corresponding to a page of the set of pages, wherein the buffer includes multiple entries for storing recently used page table entries. Each entry of the buffer may include a dirty (D) bit indicating whether or not a corresponding page of the second processor needs to be written to the storage.
A read of each page table entry of the set of page table entries is performed after the above described informing of the second processor. A read of a page table entry corresponding to the first page of the first processor is performed, wherein the page table entry includes a dirty (D) bit indicating whether or not the first bit needs to be written to the storage. The first page of the first processor is written from the memory to the storage if: (i) a dirty (D) bit of at least one page table entry obtained during the read of each page table entry of the set of page table entries indicates the corresponding page of the second processor needs to be written to the storage, or (ii) the dirty (D) bit of the page table entry obtained during the read of the page table entry of the first processor indicates the first page of the first processor needs to be written to the storage.
In other embodiments, both the present (P) bit and the dirty (D) bit of each page table entry of the set of page table entries may be cleared during the above described marking. In such embodiments, the accessing of each page table entry of the set of page table entries may include a first read operation, and the above described reading of each page table entry of the set of page table entries, performed after the informing, may constitute a second read operation. The first page of the first processor may be written from the memory to the storage if: (i) a dirty (D) bit of at least one page table entry obtained during the first read operation indicates the corresponding page of the second processor needs to be written to the storage, or (ii) a dirty (D) bit of at least one page table entry obtained during the second read operation indicates the corresponding page of the second processor needs to be written to the storage, or (iii) the dirty (D) bit of the page table entry obtained during the read of the page table entry of the first processor indicates the first page of the first processor needs to be written to the storage.
The virtual memory page replacement method may include responding to the above described informing of the second processor by: (i) locating an entry of the buffer corresponding to a page of the set of pages; (ii) if the dirty (D) bit of the entry corresponding to the page of the set of pages indicates the page of the set of pages needs to be written to the storage, updating the dirty (D) bit of the page table entry of the second processor corresponding to the page of the set of pages to indicate that the page of the set of pages needs to be written to the storage; and (iii) clearing the entry corresponding to the page of the set of pages.
The above described informing of the second processor may include sending a message to the second processor indicating a need to clear any entry of the buffer of the second processor corresponding to a page of the set of pages.
The virtual memory page replacement method may also include: (i) receiving an indication of a page fault condition in the second processor; and (ii) determining that a first page of the first processor, stored in the memory, must be replaced by a second page of the first processor, stored in the storage, to clear the page fault condition in the second processor. The above described receiving of the indication may include receiving a message from the second processor indicating a page fault condition in the second processor. The virtual memory page replacement method may also include sending a message to the second processor indicating page fault condition resolution when the page fault condition in the second processor has been resolved.
A carrier medium is described including program instructions for carrying out the virtual memory page replacement method. The carrier medium may be, for example, a computer-readable storage medium (e.g., a floppy disk or a compact disk read only memory (CD-ROM) disk).